---
id: 5900f4c51000cf542c50ffd7
title: 'Завдання 344: гра «Срібний долар»'
challengeType: 1
forumTopicId: 302003
dashedName: problem-344-silver-dollar-game
---

# --description--

Один з варіантів гри Н. Г. де Брейна «Срібний долар» можна описати таким чином:

В ряді квадратів розміщена певна кількість монет, не більше однієї на квадраті. Цінність має лише монета під назвою «срібний долар». Двоє гравців ходять по черзі. Хід може бути або звичайним, або особливим.

Звичайний хід полягає в тому, щоб вибрати одну монету і перемістити її на один чи більше квадратів ліворуч. Монета не може вийти за межі ряду, перестрибнути або накрити собою іншу монету.

Крім того, замість звичайного ходу гравець може обрати спеціальний, а саме — забрати крайню ліву монету. Якщо звичайний хід неможливий, гравець не має вибору, окрім як забрати крайню ліву монету.

Перемагає той гравець, який забирає срібний долар.

<img class="img-responsive center-block" alt="гра в срібний долар" src="https://cdn.freecodecamp.org/curriculum/project-euler/silver-dollar-game.gif" style="background-color: white; padding: 10px;" />

Виграшна конфігурація полягає у розташуванні монет в ряд таким чином, щоб перший гравець переміг незалежно від дій другого гравця.

Нехай $W(n, c)$ буде кількістю виграшних конфігурацій ряду з $n$ квадратів, $c$ непотрібних монет та одного срібного долара.

Дано, що $W(10, 2) = 324$ та $W(100, 10) = 1\\,514\\,704\\,946\\,113\\,500$.

Знайдіть $W(1\\,000\\,000, 100)$ за модулем напівпростого числа $1000\\,036\\,000\\,099 (= 1\\,000\\,003 \times 1\\,000\\,033)$.

# --hints--

`silverDollarGame()` має повернути `65579304332`.

```js
assert.strictEqual(silverDollarGame(), 65579304332);
```

# --seed--

## --seed-contents--

```js
function silverDollarGame() {

  return true;
}

silverDollarGame();
```

# --solutions--

```js
// solution required
```
